package E.哈希表;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class _350_两个数组的交集II {
    /**
     * 自解：将长的那个存在hash表里 key为数值 value为频次
     * 遍历小的那个 如果contain 就输出到结果
     * boolean true表示nums1小
     * ---时间O(m+n) 空间O(min(m,n))
     * ---运行：耗时9.22% 空间74.27%
     *      * -----优化：降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersect(int[] nums1, int[] nums2) {

        HashMap<Integer,Integer> map;

        if (nums1.length>nums2.length){
           map = insert(nums2);
           return compare(map,nums1);
        }

        map = insert(nums1);
        return compare(map,nums2);




    }
    public HashMap<Integer,Integer> insert(int[] nums){
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int num:nums){
            int count = map.containsKey(num)?map.get(num)+1:1;
            map.put(num,count);
        }

        return map;

    }
    public int[] compare(HashMap<Integer,Integer> map,int[] nums){
        ArrayList<Integer> list = new ArrayList<>();
        for (int num:nums){
            if (map.containsKey(num) && map.get(num)>0){
                list.add(num);
                map.put(num,map.get(num)-1);
            }

        }

        return list.stream().mapToInt(Integer::valueOf).toArray();
    }

    /**
     * 方法二：排序--双指针法
     * 如果两个数组是有序的，则可以便捷地计算两个数组的交集。
     *
     * 首先对两个数组进行排序，然后使用两个指针遍历两个数组。
     *
     * 初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束
     *如果 元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中。那么就无法高效地对 num2进行排序，因此推荐使用方法一而不是方法二。
     * 在方法一中，2nums2只关系到查询操作，因此每次读取 nums2中的一部分数据，并进行处理即可。
     *

     */

    public int[] intersect1(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        ArrayList<Integer> list = new ArrayList<>();
        int i=0,j=0;
        while (i != nums1.length && j != nums2.length){
            if (nums1[i] < nums2[j]){
                i++;
            }else if (nums1[i] > nums2[j]){
                j++;
            }else {
                list.add(nums1[i] );
                i++;
                j++;
            }
        }

        return list.stream().mapToInt(Integer::valueOf).toArray();
    }

}
